昨天寫一寫發現自己對graph了解實在薄弱
dijks算法也很弱

繼續加強相關題目熟悉度

Detonate the Maximum Bombs

Q: https://leetcode.com/problems/detonate-the-maximum-bombs/

class Solution {
    public int maximumDetonation(int[][] bombs) {
        int max = 0;
        for (int i = 0;i < bombs.length;i++) {
            int count = explode(bombs, i);
            max = Math.max(max, count);
        }
        return max;
    }

    private int explode(int[][] bombs, int start) {
        boolean[] isExploded = new boolean[bombs.length];
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        int count = 1;
        isExploded[start] = true;
        while(!q.isEmpty()) {
            int now = q.poll();
            int x = bombs[now][0];
            int y = bombs[now][1];
            long r = bombs[now][2];
            for (int i = 0;i < bombs.length;i++) {
                if (!isExploded[i]) {
                    long e1 =  Math.abs(x - bombs[i][0]);
                    long e2 =  Math.abs(y - bombs[i][1]);
                    long distance = (e1 * e1) + (e2 * e2);
                    if (r * r >= distance) {
                        isExploded[i] = true;
                        count++;
                        q.offer(i);
                    }
                }
            }
        }
        return count;
    }
}

tips: 處理數字時需要小心 數值如果出了邊界會有錯誤Q__Q

Find the City With the Smallest Number of Neighbors at a Threshold Distance

Q: https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int min = n-1;
        int result = -1;
        Map<Integer, List<int[]>> toCityWithWeightByCity = new HashMap<>();
        for (int[] edge : edges) {
            if (!toCityWithWeightByCity.containsKey(edge[0])) {
                toCityWithWeightByCity.put(edge[0], new ArrayList<>());
            }
            if (!toCityWithWeightByCity.containsKey(edge[1])) {
                toCityWithWeightByCity.put(edge[1], new ArrayList<>());
            }
            toCityWithWeightByCity.get(edge[0]).add(new int[]{edge[1], edge[2]});
            toCityWithWeightByCity.get(edge[1]).add(new int[]{edge[0], edge[2]});
        }
        for (int i = 0;i < n;i++) {
            int count = getCount(n, i, toCityWithWeightByCity, distanceThreshold);
            if (count <= min) {
                min = count;
                result = i;
            }
        }
        return result;
    }

    private int getCount(int n, int start, 
        Map<Integer, List<int[]>> toCityWithWeightByCity, int distanceThreshold) {
        int[] distance = new int[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        Queue<Integer> q = new LinkedList<>();
        distance[start] = 0;
        q.offer(start);
        while(!q.isEmpty()) {
            int now = q.poll();
            List<int[]> toCityWithWeights = toCityWithWeightByCity.get(now);
            if (null != toCityWithWeights) {
                for (int[] toCityWithWeight : toCityWithWeights) {
                    int toCity = toCityWithWeight[0];
                    int weight = toCityWithWeight[1];
                    if (distance[now] + weight < distance[toCity]) {
                        distance[toCity] = distance[now] + weight;
                        q.offer(toCity);
                    }
                }
            }
        }
        int count = 0;
        for (int d : distance) {
            if (d!= 0 && d <= distanceThreshold) {
                count++;
            }
        }
        return count;
    }
}

利用dijks算法算出到每個點的最短路徑
tips: 遇到無方向圖 需要先建圖會比較好處理

Design Graph With Shortest Path Calculator

Q: https://leetcode.com/problems/design-graph-with-shortest-path-calculator/

class Graph {
    
    int[][] shortestPaths; // shortestPaths[i][j] node i -> node j distance
    Map<Integer, List<int[]>> outboundWithPathByNode = new HashMap<>();

    public Graph(int n, int[][] edges) {
        shortestPaths = new int[n][n];
        for (int i = 0;i < n;i++) {
            for (int j = 0;j < n;j++) {
                if (i == j) {
                    shortestPaths[i][j] = 0;
                } else {
                    shortestPaths[i][j] = -1;
                }
            }
        }
        for (int[] edge : edges) {
            if (!outboundWithPathByNode.containsKey(edge[0])) {
                outboundWithPathByNode.put(edge[0], new ArrayList<>());
            }
            outboundWithPathByNode.get(edge[0]).add(new int[]{edge[1], edge[2]});
        }
        dijks();
    }
    
    public void addEdge(int[] edge) {
        if (!outboundWithPathByNode.containsKey(edge[0])) {
            outboundWithPathByNode.put(edge[0], new ArrayList<>());
        }
        for (int i = 0;i < shortestPaths.length;i++) {
            for (int j = 0;j < shortestPaths.length;j++) {
                if (i == j) {
                    shortestPaths[i][j] = 0;
                } else {
                    shortestPaths[i][j] = -1;
                }
            }
        }
        outboundWithPathByNode.get(edge[0]).add(new int[]{edge[1], edge[2]});
        dijks();
    }
    
    public int shortestPath(int node1, int node2) {
        return shortestPaths[node1][node2];
    }

    private void dijks() {
        for (int i = 0;i < shortestPaths.length;i++) {
            setSortestPathByNode(i);
        }
    }

    private void setSortestPathByNode(int i) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(i);
        while(!q.isEmpty()) {
            int now = q.poll();
            List<int[]> outboundWithPath = outboundWithPathByNode.get(now);
            int distance = shortestPaths[i][now];
            if (null != outboundWithPath) {
                for (int[] arr : outboundWithPath) {
                    int toNode = arr[0];
                    int weight = arr[1];
                    if (shortestPaths[i][toNode] == -1 || shortestPaths[i][toNode] > distance + weight) {
                        shortestPaths[i][toNode] = distance + weight;
                        q.offer(toNode);
                    } 
                }
            }
        }
    }
}

/**
 * Your Graph object will be instantiated and called as such:
 * Graph obj = new Graph(n, edges);
 * obj.addEdge(edge);
 * int param_2 = obj.shortestPath(node1,node2);
 */

...感覺應該還可以再優化